/**
 * 给若干个矩形，求一个y=未知的直线，使得该直线恰好平分上下面积。
 * 显然可以二分，然后用扫描线求面积。因为N为5E4，扫描线求一次面积为NlogN
 * 所以总复杂度为 log(1E9) * 5E4 * log(5E4)
 * 按理来说是可以过的，但是到第694个用例超时，一共698个用例。
 * 不确定是否是模板的常数问题，或者二分的常数问题。
 * 但实际上扫描线只需要调用一遍即可，用数组记录每根扫描线当时已经扫出的面积，
 * 然后在这个数组上就能找出那根线可以平分面积。
 * 这个数组处理稍微有点麻烦，因为多根扫描线事件会重合，因此这个数组中有可能存在多个相等的元素。
 * 如果二分的话，要保证正确且在所有情况下都不会退化到线性，还有点麻烦。
 * 实际上无需二分，因为扫描线的结果数组就是O(2N)，从左到右做一个枚举即可。
 * 修改了一下OY的模板，使之可以带出扫描线结果数组。
 * 模板默认是扫X的，要扫y只需要输入时坐标互换一下即可
 */

#ifdef _MSC_VER
#define CPP_STANDARD _MSVC_LANG
#else
#define CPP_STANDARD __cplusplus
#endif
#if CPP_STANDARD >= 201402L
#define CONSTEXPR_IF_CPP14 constexpr
#else
#define CONSTEXPR_IF_CPP14
#endif

namespace std {
    namespace my_bit_ops {
        static constexpr int s32[32] = {31, 0, 1, 5, 2, 10, 6, 15, 3, 13, 11, 20, 7, 22, 16, 25, 30, 4, 9, 14, 12, 19, 21, 24, 29, 8, 18, 23, 28, 17, 27, 26};
        static constexpr int s64[64] = {63, 0, 1, 6, 2, 12, 7, 18, 3, 24, 13, 27, 8, 33, 19, 39, 4, 16, 25, 37, 14, 45, 28, 47, 9, 30, 34, 53, 20, 49, 40, 56, 62, 5, 11, 17, 23, 26, 32, 38, 15, 36, 44, 46, 29, 52, 48, 55, 61, 10, 22, 31, 35, 43, 51, 54, 60, 21, 42, 50, 59, 41, 58, 57};
        static constexpr int s256[256] = {8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        static constexpr int ctz32(uint32_t x) noexcept { return s32[(x & -x) * 0b00001000110010100111010110111110 >> 27]; }
        static constexpr int ctz64(uint64_t x) noexcept { return s64[(x & -x) * 0b0000010000110001010001110010010110011010011110101011101101111110 >> 58]; }
        static constexpr int clz8(uint32_t x) noexcept { return s256[x]; }
        static constexpr int clz16(uint32_t x) noexcept { return x >> 8 ? clz8(x >> 8) : 8 + clz8(x); }
        static constexpr int clz32(uint32_t x) noexcept { return x >> 16 ? clz16(x >> 16) : 16 + clz16(x); }
        static constexpr int clz64(uint64_t x) noexcept { return x >> 32 ? clz32(x >> 32) : 32 + clz32(x); }
        static constexpr uint32_t f1_32(uint32_t x) noexcept { return x - ((x >> 1) & 0x55555555); }
        static constexpr uint32_t f2_32(uint32_t x) noexcept { return (x & 0x33333333) + ((x >> 2) & 0x33333333); }
        static constexpr int f3_32(uint32_t x) noexcept { return (x + (x >> 4) & 0x0f0f0f0f) * 0x01010101 >> 24; }
        static constexpr int popcnt32(uint32_t x) noexcept { return f3_32(f2_32(f1_32(x))); }
        static constexpr uint64_t f1_64(uint64_t x) noexcept { return x - ((x >> 1) & 0x5555555555555555); }
        static constexpr uint64_t f2_64(uint64_t x) noexcept { return (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); }
        static constexpr int f3_64(uint64_t x) noexcept { return (x + (x >> 4) & 0x0f0f0f0f0f0f0f0f) * 0x0101010101010101 >> 56; }
        static constexpr int popcnt64(uint64_t x) noexcept { return f3_64(f2_64(f1_64(x))); }
        constexpr uint32_t bit_ceil_msvc_32(uint32_t x) noexcept { return x ? uint32_t(1) << (32 - clz32(x - 1)) : 1; }
        constexpr uint64_t bit_ceil_msvc_64(uint64_t x) noexcept { return x ? uint64_t(1) << (64 - clz64(x - 1)) : 1; }
        template <typename Tp>
        constexpr Tp bit_ceil_msvc(Tp x) noexcept { return sizeof(Tp) == 4 ? bit_ceil_msvc_32(x) : bit_ceil_msvc_64(x); }
        constexpr uint32_t bit_floor_msvc_32(uint32_t x) noexcept { return x ? uint32_t(1) << (31 - clz32(x)) : 0; }
        constexpr uint64_t bit_floor_msvc_64(uint64_t x) noexcept { return x ? uint64_t(1) << (63 - clz64(x)) : 0; }
        template <typename Tp>
        constexpr Tp bit_floor_msvc(Tp x) noexcept { return sizeof(Tp) == 4 ? bit_floor_msvc_32(x) : bit_floor_msvc_64(x); }
        constexpr uint32_t bit_width_msvc_32(uint32_t x) noexcept { return 32 - clz32(x); }
        constexpr uint64_t bit_width_msvc_64(uint64_t x) noexcept { return 64 - clz64(x); }
        template <typename Tp>
        constexpr Tp bit_width_msvc(Tp x) noexcept { return sizeof(Tp) == 4 ? bit_width_msvc_32(x) : bit_width_msvc_64(x); }
        constexpr int countl_zero_msvc_32(uint32_t x) noexcept { return x ? clz32(x) : 32; }
        constexpr int countl_zero_msvc_64(uint64_t x) noexcept { return x ? clz64(x) : 64; }
        template <typename Tp>
        constexpr int countl_zero_msvc(Tp x) noexcept { return sizeof(Tp) == 4 ? countl_zero_msvc_32(x) : countl_zero_msvc_64(x); }
        constexpr int countr_zero_msvc_32(uint32_t x) noexcept { return x ? ctz32(x) : 32; }
        constexpr int countr_zero_msvc_64(uint64_t x) noexcept { return x ? ctz64(x) : 64; }
        template <typename Tp>
        constexpr int countr_zero_msvc(Tp x) noexcept { return sizeof(Tp) == 4 ? countr_zero_msvc_32(x) : countr_zero_msvc_64(x); }
        template <typename Tp>
        constexpr int popcount_msvc(Tp x) noexcept { return sizeof(Tp) == 4 ? popcnt32(x) : popcnt64(x); }
#ifdef _MSC_VER
        template <typename Tp>
        constexpr Tp bit_ceil(Tp x) noexcept { return bit_ceil_msvc(x); }
        template <typename Tp>
        constexpr Tp bit_floor(Tp x) noexcept { return bit_floor_msvc(x); }
        template <typename Tp>
        constexpr Tp bit_width(Tp x) noexcept { return bit_width_msvc(x); }
        template <typename Tp>
        constexpr int countl_zero(Tp x) noexcept { return countl_zero_msvc(x); }
        template <typename Tp>
        constexpr int countr_zero(Tp x) noexcept { return countr_zero_msvc(x); }
        template <typename Tp>
        constexpr int popcount(Tp x) noexcept { return popcount_msvc(x); }
#else
        constexpr uint32_t bit_ceil_32(uint32_t x) noexcept { return x > 1 ? uint32_t(1) << (32 - __builtin_clz(x - 1)) : 1; }
        constexpr uint64_t bit_ceil_64(uint64_t x) noexcept { return x > 1 ? uint64_t(1) << (64 - __builtin_clzll(x - 1)) : 1; }
        template <typename Tp>
        constexpr Tp bit_ceil(Tp x) noexcept { return sizeof(Tp) == 4 ? bit_ceil_32(x) : bit_ceil_64(x); }
        constexpr uint32_t bit_floor_32(uint32_t x) noexcept { return x ? uint32_t(1) << (31 - __builtin_clz(x)) : 0; }
        constexpr uint64_t bit_floor_64(uint64_t x) noexcept { return x ? uint64_t(1) << (63 - __builtin_clzll(x)) : 0; }
        template <typename Tp>
        constexpr Tp bit_floor(Tp x) noexcept { return sizeof(Tp) == 4 ? bit_floor_32(x) : bit_floor_64(x); }
        constexpr uint32_t bit_width_32(uint32_t x) noexcept { return x ? 32 - __builtin_clz(x) : 0; }
        constexpr uint64_t bit_width_64(uint64_t x) noexcept { return x ? 64 - __builtin_clzll(x) : 0; }
        template <typename Tp>
        constexpr Tp bit_width(Tp x) noexcept { return sizeof(Tp) == 4 ? bit_width_32(x) : bit_width_64(x); }
        constexpr int countl_zero_32(uint32_t x) noexcept { return x ? __builtin_clz(x) : 32; }
        constexpr int countl_zero_64(uint64_t x) noexcept { return x ? __builtin_clzll(x) : 64; }
        template <typename Tp>
        constexpr int countl_zero(Tp x) noexcept { return sizeof(Tp) == 4 ? countl_zero_32(x) : countl_zero_64(x); }
        constexpr int countr_zero_32(uint32_t x) noexcept { return x ? __builtin_ctz(x) : 32; }
        constexpr int countr_zero_64(uint64_t x) noexcept { return x ? __builtin_ctzll(x) : 64; }
        template <typename Tp>
        constexpr int countr_zero(Tp x) noexcept { return sizeof(Tp) == 4 ? countr_zero_32(x) : countr_zero_64(x); }
        template <typename Tp>
        constexpr int popcount(Tp x) noexcept { return sizeof(Tp) == 4 ? __builtin_popcount(x) : __builtin_popcountll(x); }
#endif
    }
#ifndef __cpp_lib_bitops
    using my_bit_ops::bit_ceil;
    using my_bit_ops::bit_floor;
    using my_bit_ops::bit_width;
    using my_bit_ops::countl_zero;
    using my_bit_ops::countr_zero;
    using my_bit_ops::popcount;
#endif
}



namespace RU {

using size_type = uint64_t;

/**
 * @brief 线段树
 */
template <typename Tp> class CoverTree {
public:
struct node {
    Tp m_sum, m_area;
    size_type m_tag;
    Tp get() const { return m_tag ? m_area : m_sum; }
};
    
private:
size_type m_size, m_cap;
std::vector<node> m_sub;

/// 更新，就是求和
static void _update(node *sub, size_type i) { sub[i].m_sum = sub[i * 2].get() + sub[i * 2 + 1].get(); }
       
template <typename Callback>
void _work(size_type left, size_type right, Callback &&call) {
    auto sub = m_sub.data();
    size_type cur = left;
    if (cur)
        while (true) {
            size_type j = std::countr_zero(cur), nxt = cur + (size_type(1) << j);
            if (nxt > right) break;
            call(sub + ((m_cap + cur) >> j));
            for (size_type i = (m_cap + cur) >> j, end = nxt < right ? (m_cap + nxt) >> (std::countr_zero(nxt) + 1) : 0; (i >>= 1) != end;) _update(sub, i);
            cur = nxt;
        }
    while (cur < right) {
        size_type j = std::bit_width(cur ^ right), nxt = cur + (size_type(1) << (j - 1));
        call(sub + ((m_cap + cur) >> (j - 1)));
        for (size_type i = (m_cap + cur) >> (j - 1), end = nxt < right ? (m_cap + cur) >> j : 0; (i >>= 1) != end;) _update(sub, i);
        cur = nxt;
    }
}

public:
CoverTree() = default;

/**
 * @brief 线段树初始化
 * 
 * @tparam InitMapping 
 * @param length 
 * @param mapping 
 */
template <typename InitMapping>CoverTree(size_type length, InitMapping mapping) {
    m_cap = std::bit_ceil(m_size = length);
    m_sub.assign(m_cap * 2, {});
    for (size_type i = 0; i != m_size; i++) m_sub[m_cap + i].m_area = mapping(i);
    for (size_type len = m_cap / 2, cnt = (m_size + 1) / 2, w = 2; len; len >>= 1, cnt = (cnt + 1) / 2, w <<= 1)
        for (size_type i = len; i != len + cnt; i++) m_sub[i].m_area = m_sub[i * 2].m_area + m_sub[i * 2 + 1].m_area;
}

void add(size_type left, size_type right) {
    _work(left, right, [](node *p) { ++p->m_tag; });
}
void remove(size_type left, size_type right) {
    _work(left, right, [](node *p) { --p->m_tag; });
}
Tp query_all() const { return m_sub[1].get(); }
};

/**
 * @brief 扫描线外包装类
 * @tparam SizeType 指坐标的尺寸，坐标是用格子来标记的
 *  即 [1, 3]代表第1格、第2格、第3格，一共三格，长度为3；
 *   而不是点1、点2、点3，此表示法长度实际上只有2
 */
template <typename SizeType> class Solver {
public:
/// 扫描线事件
struct event {
    SizeType m_time, m_low, m_high;
    bool operator<(const event &rhs) const { return m_time < rhs.m_time; }
};
struct pair {
    SizeType m_val;
    size_type m_index;
    bool operator<(const pair &rhs) const { return m_val < rhs.m_val; }
};
private:
std::vector<event> m_es; // 事件的集合
std::vector<pair> m_ps;  // 
public:
/// 默认构造函数
Solver(size_type rect_cnt = 0) { m_es.reserve(rect_cnt * 2), m_ps.reserve(rect_cnt * 2); }

/**
 * @brief 加入矩形，注意坐标的含义如上所示，表示格，而不是点
 */
void add_rect(SizeType x_min, SizeType x_max, SizeType y_min, SizeType y_max) {
    m_es.push_back({x_min});
    m_es.push_back({x_max + 1});
    m_ps.push_back({y_min, (size_type)m_ps.size()});
    m_ps.push_back({y_max + 1, (size_type)m_ps.size()});
}

/**
 * @brief 求解的主方法，这是一个模板方法
 *  典型的如构造Solver的时候使用int，此处求解则大概率要用longlong
 * @param areaBeforeX 不为空时，记录每个x坐标左边的面积 [(面积, x坐标)]
 *  如果想求y坐标，可以在构造矩形的时候将x/y坐标互换
 */
template <typename SumType = SizeType> SumType solve(std::vector<std::pair<SumType, SizeType>> * areaBeforeX = nullptr) {
    /// 按y坐标排序
    std::sort(m_ps.begin(), m_ps.end());
    std::vector<SizeType> ys;
    ys.reserve(m_ps.size());
    for (size_type i = 0; i != m_ps.size(); i++) {
        if (!i || m_ps[i].m_val != m_ps[i - 1].m_val) ys.push_back(m_ps[i].m_val);
        m_es[m_ps[i].m_index].m_low = m_es[m_ps[i].m_index ^ 1].m_high = ys.size() - 1;
    }
    std::sort(m_es.begin(), m_es.end());
    CoverTree<SizeType> S(ys.size() - 1, [&](size_type i) { return ys[i + 1] - ys[i]; });
    SumType h{}, last{}, ans{};
    if(areaBeforeX) // 还要记录每一根扫描线下的面积
    {
        areaBeforeX->clear();
        areaBeforeX->reserve(m_es.size());

        for (auto &e : m_es) {
            ans += h * (e.m_time - last);
            areaBeforeX->emplace_back(ans, last = e.m_time);
            if (e.m_low < e.m_high)
                S.add(e.m_low, e.m_high);
            else
                S.remove(e.m_high, e.m_low);
            h = S.query_all();
        }

    }
    else // 直接求并的总面积
    {
        for (auto &e : m_es) {
            ans += h * (e.m_time - last);
            last = e.m_time;
            if (e.m_low < e.m_high)
                S.add(e.m_low, e.m_high);
            else
                S.remove(e.m_high, e.m_low);
            h = S.query_all();
        }        
    }

    return ans;
}

};

}

class Solution {
public:
    double separateSquares(vector<vector<int>>& squares) {
        using llt = long long;
        RU::Solver<int> sol;
        for(auto & v : squares){
            swap(v[0], v[1]); // x/y坐标互换
            sol.add_rect(v[0], v[0] + v[2] - 1, v[1], v[1] + v[2] - 1);
        }
        std::vector<std::pair<llt, int>> vec;
        sol.solve<llt>(&vec);

        auto total = vec.back().first;
        /// 在vec中找到第一个地方，使得左边等于右边
        for(int i=0;i<vec.size();++i){
            auto zuo = vec[i].first;
            auto you = total - zuo;
            if(zuo == you){ // 相等直接返回
                return vec[i].second;
            }else if(zuo > you){ // 说明就在i-1与i之间
                auto zuo = vec[i - 1].first;
                auto you = total - vec[i].first;
                auto zh = total - zuo - you;
                auto frac = (double)(zh + you - zuo) / (zh + zh);
                return vec[i - 1].second + frac * (vec[i].second - vec[i - 1].second);         
            }
        }
        assert(0);
        return 1E300;
    }
};